package com.zwj.interview.单调栈;

import java.util.Stack;

/**
 * @Author: Zwj
 * @Date: 2022/2/28 11:14
 * 现在是的之前的例子基础上，数组的效果编程环形的了
 * 比如:数组为:[2,1,2,4,3] 输出结果为：[4,2,4,-1,4]
 */
public class 下一个更大的数3 {

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Stack<Integer> s = new Stack<>();
        int[] ans = new int[n];
        //将原数组复制一份加载原数组上，这样的话新的数组长度为2n
        for (int i = 2 * n - 1; i >= 0; i--) {
            while (!s.isEmpty() && s.peek() <= nums[i % n]) {
                s.pop();
            }
            ans[i % n] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i % n]);
        }
        return ans;
    }

}